/*
 * Copyright Aduna (http://www.aduna-software.com/) (c) 1997-2006.
 *
 * Licensed under the Aduna BSD-style license.
 */

package edu.tju.commons.text;

import java.util.HashSet;
import java.util.Iterator;
import java.util.StringTokenizer;

public class StringSearch {

	/**
	 * Find keywords specified by an 'AltaVista'-like search string. Eg: "san
	 * francisco" +"golden gate" -alcatr* NOTE: '+' in user input must be
	 * replaced by '%2B' in search string ' ' in user input must be replaced by
	 * '%20' in search string
	 * 
	 * @param text
	 *            the text to search in
	 * @param searchString
	 *            an 'AltaVista'-like search string
	 * @param caseSensitive
	 *            is the search case-sensistive?
	 * @return an integer indicating the relevance of the text, where -1
	 *         indicates a violation of the search query where 0 indicates
	 *         irrelevance where N indicates the relevance of the search
	 */
	public static int find(String text, String searchString,
			boolean caseSensitive) {
		if (!caseSensitive) {
			searchString = searchString.toLowerCase();
			text = text.toLowerCase();
		}
		text = StringUtil.gsub("\n", " ", text);
		text = StringUtil.gsub("\t", " ", text);
		text = StringUtil.gsub("\r", " ", text);
		text = StringUtil.gsub("\f", " ", text);

		// Parse the searchString
		HashSet<String> includeTokens = new HashSet<String>();
		HashSet<String> excludeTokens = new HashSet<String>();
		HashSet<String> neutralTokens = new HashSet<String>();

		// first, extract all quoted tokens (and delete them from searchString)
		// Note: '*' is not supported for a quoted expression
		String quotedToken = null;
		int openQuoteIndex = searchString.indexOf("\"");
		while (openQuoteIndex >= 0 && searchString.length() > 1) {
			StringBuilder tmpBuf = new StringBuilder(searchString);

			int closeQuoteIndex = searchString
					.indexOf("\"", openQuoteIndex + 1);
			if (closeQuoteIndex < 0) {
				closeQuoteIndex = searchString.indexOf(" ", openQuoteIndex + 1);
				if (closeQuoteIndex < 0) {
					closeQuoteIndex = searchString.length();
				}
			}

			quotedToken = searchString.substring(openQuoteIndex + 1,
					closeQuoteIndex);
			tmpBuf.delete(openQuoteIndex, closeQuoteIndex + 1);

			if (openQuoteIndex > 0) {
				if (searchString.charAt(openQuoteIndex - 1) == '+') {
					includeTokens.add(quotedToken);
					tmpBuf.deleteCharAt(openQuoteIndex - 1);
				} else if (searchString.charAt(openQuoteIndex - 1) == '-') {
					excludeTokens.add(quotedToken);
					tmpBuf.deleteCharAt(openQuoteIndex - 1);
				} else {
					neutralTokens.add(quotedToken);
				}
			} else {
				neutralTokens.add(quotedToken);
			}

			searchString = tmpBuf.toString();
			openQuoteIndex = searchString.indexOf("\"", closeQuoteIndex + 1);
		}

		// then, extract all unquoted tokens '+' and '-' are removed, but '*' is
		// retained
		StringTokenizer strtok = new StringTokenizer(searchString); // default
		// delimiters
		while (strtok.hasMoreTokens()) {
			String token = strtok.nextToken();

			if (token.startsWith("+")) {
				includeTokens.add(token.substring(1));
			} else if (token.startsWith("-")) {
				excludeTokens.add(token.substring(1));
			} else {
				neutralTokens.add(token);
			}
		}

		// Calculate the result
		int result = 0;

		// include tokens ('+') *must* appear in text and add to the relevance
		Iterator<String> it = includeTokens.iterator();
		while (it.hasNext() && result >= 0) {
			String includeToken = it.next();
			if (!contains(text, includeToken)) {
				result = -1;
			} else {
				result++;
			}
		}

		// exclude tokens ('-') *must not* appear in the text
		if (result >= 0) {
			it = excludeTokens.iterator();
			while (it.hasNext() && result >= 0) {
				String excludeToken = it.next();
				if (contains(text, excludeToken)) {
					result = -1;
				}
			}
		}

		// neutral tokens add to the relevance of the result
		if (result >= 0) {
			it = neutralTokens.iterator();
			while (it.hasNext()) {
				String neutralToken = it.next();
				if (contains(text, neutralToken)) {
					result++;
				}
			}
		}

		return result;
	}

	/**
	 * Find keywords specified by an 'AltaVista'-like search string. This method
	 * allows you to do a slightly more efficient search at the cost of getting
	 * only 1 when the text matches the query or -1 when it does not.
	 * 
	 * @param text
	 *            the text to search in
	 * @param searchString
	 *            an 'AltaVista'-like search string
	 * @param caseSensitive
	 *            is the search case-sensistive?
	 * @param relevance
	 *            should we report relevance count or simply 'match' (1) or 'no
	 *            match' (-1)?
	 * @return an integer indicating the relevance of the text, where -1
	 *         indicates a violation of the search query (no match). where 0
	 *         indicates irrelevance (when relevance is true). where N indicates
	 *         the relevance of the search, or 1 indicates the searchString
	 *         matched (when relevance is false).
	 */
	public static int find(String text, String searchString,
			boolean caseSensitive, boolean relevance) {
		if (relevance) {
			return find(text, searchString, caseSensitive);
		}

		if (!caseSensitive) {
			searchString = searchString.toLowerCase();
			text = text.toLowerCase();
		}
		text = StringUtil.gsub("\n", " ", text);
		text = StringUtil.gsub("\t", " ", text);
		text = StringUtil.gsub("\r", " ", text);
		text = StringUtil.gsub("\f", " ", text);

		// Parse the searchString
		HashSet<String> includeTokens = new HashSet<String>();
		HashSet<String> excludeTokens = new HashSet<String>();
		HashSet<String> neutralTokens = new HashSet<String>();

		// first, extract all quoted tokens (and delete them from searchString)
		// Note: '*' is not supported for a quoted expression
		String quotedToken = null;
		int openQuoteIndex = searchString.indexOf("\"");
		while (openQuoteIndex >= 0 && searchString.length() > 1) {
			StringBuilder tmpBuf = new StringBuilder(searchString);

			int closeQuoteIndex = searchString
					.indexOf("\"", openQuoteIndex + 1);
			if (closeQuoteIndex < 0) {
				closeQuoteIndex = searchString.indexOf(" ", openQuoteIndex + 1);
				if (closeQuoteIndex < 0) {
					closeQuoteIndex = searchString.length();
				}
			}

			quotedToken = searchString.substring(openQuoteIndex + 1,
					closeQuoteIndex);
			tmpBuf.delete(openQuoteIndex, closeQuoteIndex + 1);

			if (openQuoteIndex > 0) {
				if (searchString.charAt(openQuoteIndex - 1) == '+') {
					includeTokens.add(quotedToken);
					tmpBuf.deleteCharAt(openQuoteIndex - 1);
				} else if (searchString.charAt(openQuoteIndex - 1) == '-') {
					excludeTokens.add(quotedToken);
					tmpBuf.deleteCharAt(openQuoteIndex - 1);
				} else {
					neutralTokens.add(quotedToken);
				}
			} else {
				neutralTokens.add(quotedToken);
			}

			searchString = tmpBuf.toString();
			openQuoteIndex = searchString.indexOf("\"", closeQuoteIndex + 1);
		}

		// then, extract all unquoted tokens
		// '+' and '-' are removed, but '*' is retained
		StringTokenizer strtok = new StringTokenizer(searchString); // default
		// delimiters
		while (strtok.hasMoreTokens()) {
			String token = strtok.nextToken();

			if (token.startsWith("+")) {
				includeTokens.add(token.substring(1));
			} else if (token.startsWith("-")) {
				excludeTokens.add(token.substring(1));
			} else {
				neutralTokens.add(token);
			}
		}

		// include tokens ('+') *must* appear in text.
		Iterator<String> it = includeTokens.iterator();
		while (it.hasNext()) {
			String includeToken = it.next();
			if (!contains(text, includeToken)) {
				return -1; // text does not match query. Exit immediately.
			}
		}

		// exclude tokens ('-') *must not* appear in the text
		it = excludeTokens.iterator();
		while (it.hasNext()) {
			String excludeToken = it.next();
			if (contains(text, excludeToken)) {
				return -1; // text does not match query. Exit immediately.
			}
		}

		// neutral tokens may or may not appear. as soon as one does, the
		// text matches the search string, since include and exclude
		// tokens already matched at this point.
		it = neutralTokens.iterator();
		while (it.hasNext()) {
			String neutralToken = it.next();
			if (contains(text, neutralToken)) {
				return 1; // text matches query. Exit immediately.
			}
		}

		if (!(includeTokens.isEmpty() && excludeTokens.isEmpty())) {
			// There were either include tokens or exclude tokens
			// specified. Since we got here, this means the text matched
			// them.
			return 1;
		} else {
			// there was no match at all.
			return -1;
		}
	}

	/**
	 * Does the text contain the specified token?
	 * 
	 * @param text
	 *            the text to search
	 * @param token
	 *            the token to look for
	 * @return true if the text contains the specified token, false otherwise.
	 */
	public static boolean contains(String text, String token) {
		String DELIMITERS = " .,/\\?!`'~#$%^&*()-_=+|[]{}";

		boolean result = false;
		int tokenLength = token.length();
		int textLength = text.length();

		if (token.startsWith("*") && token.endsWith("*") && tokenLength > 2) {
			result = text.indexOf(token.substring(1, tokenLength - 1)) >= 0;
		} else if (token.startsWith("*") && tokenLength > 1) {
			// remove * to make the new search-string
			String stoken = token.substring(1, tokenLength);
			int stokenLength = stoken.length();
			int position = text.indexOf(stoken, 0);
			while (!result && position >= 0) {
				result = (position + stokenLength >= textLength)
						|| (DELIMITERS.indexOf(text.charAt(position
								+ stokenLength)) >= 0);
				position = text.indexOf(stoken, position + 1);
			}
		} else if (token.endsWith("*") && tokenLength > 1) {
			// remove * to make the new search-string
			String stoken = token.substring(0, tokenLength - 1);
			int position = text.indexOf(stoken, 0);
			while (!result && position >= 0) {
				result = (position == 0)
						|| (DELIMITERS.indexOf(text.charAt(position - 1)) >= 0);
				position = text.indexOf(stoken, position + 1);
			}
		} else if (containsDelimiter(token, DELIMITERS)) {
			result = text.indexOf(token) >= 0;
		} else {
			result = containsWord(token, text, DELIMITERS);
		}

		return result;
	}

	private static boolean containsWord(String word, String text,
			String delimiters) {
		boolean result = false;

		StringTokenizer strtok = new StringTokenizer(text, delimiters);

		while (strtok.hasMoreTokens()) {
			String token = strtok.nextToken();
			if (token.equals(word)) {
				result = true;
				break;
			}
		}
		return result;
	}

	private static boolean containsDelimiter(String text, String delimiters) {
		StringTokenizer strtok = new StringTokenizer(text, delimiters);
		return strtok.countTokens() > 1;
	}
}
